package main.leetcode.offer.firstround.from03to50;

/**
 * 43.1~n整数中1出现的次数
 *
 * <p>输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
 *
 * <p>例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
 *
 * <p>
 *
 * <p>示例 1：输入：n = 12 输出：5
 *
 * <p>示例 2：输入：n = 13 输出：6
 *
 * <p>限制：1 <= n < 2^31
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex43 {
    public static void main(String[] args) {
        System.out.println(new ex43().countDigitOne(12));
    }

    // 0~9   中1的个数为：f(1) = 1
    // 0~99  中1的个数为：f(2) = 10*1+10 = 20
    // 0~999 中1的个数为：f(3) = 10*20+100 = 300
    // ... n代表9的个数，即位数
    // 0~9..9中1的个数为：f(n) = 10*f(n-1)+10^(n-1)

    // 以1678为例
    public int countDigitOne(int n) {
        if (n < 10) return n >= 1 ? 1 : 0; // 个位数，8中1的个数
        int tmp = n; // 不改变输入，暂存
        int l = 0; // 记录位数，4
        while (tmp > 0) { // 遍历得到位数
            tmp /= 10;
            ++l;
        }
        int x = (int) (Math.pow(10, l - 1)); // 100
        int hi = n / x; // 最高位，1
        tmp = hi * x; // 1000
        int next = n - tmp; // 678
        int res =
                hi > 1 // 高位是否为1
                        ? hi * (l - 1) * (x / 10) + x // 600、70中1的个数
                        : (l - 1) * (x / 10) + next + 1; // 1000中1的个数
        return res + countDigitOne(next);
    }
}
